/**
 * This class handles the basic functionality of a tic-tac-toe
 * board, such as keeping track of who has claim which spaces,
 * applying moves, and detecting wins and draws.  You will be
 * writing most of your code in this class.
 */

public class TTTBoard
{
	// Player identification, for internal bookkeeping.
	public static final int PLAYER_1 = 1;
	public static final int PLAYER_2 = -1;
	public static final int EMPTY = 0;
	public static final int DRAW = 0;
	// Symbols to show on the board for the specific players.
	// These are for display purposes only, not to be stored internally.
	public static final char PLAYER_1_MARK = 'X';
	public static final char PLAYER_2_MARK = 'O';
	public static final char EMPTY_MARK = ' ';
	
	// Note that we want to internally store the player ID, NOT the player mark.
	private int[][] boardData;
	private int rows, cols;
	public int winner; // 1: player1 wins
						// 2: player2 wins  
						// 0: draw
	
	private TTTMove prevMove, currMove;
	
	
	/**
	 * Create a new tic-tac-toe board with dimensions n by n.
	 * 
	 * @param n the number of spaces in each row and column.
	 */
	public TTTBoard(int n)
	{
		// check the validation of n 
		if (n < 3)
		{
			n = 2;
		}
		
		boardData = new int[n][n];
		rows = cols = n;
		initBoard(boardData);
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Create a new tic-tac-toe board with dimensions 3 by 3.
	 */
	public TTTBoard()
	{
		boardData = new int[3][4];
		rows = 3;
		cols = 4;
		initBoard(boardData);
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Return the number of rows in the tic-tac-toe board.
	 * 
	 * @return the number of rows in the tic-tac-toe board.
	 */
	public int getRows()
	{
		return rows;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Return the number of columns in the tic-tac-toe board.
	 * 
	 * @return the number of columns in the tic-tac-toe board.
	 */
	public int getCols()
	{
		return cols;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * initBoard -- although the new 2D array has default value 0, but I will ensure this by this function
	 * @param boardData the boardData of TTT
	 */
	private void initBoard(int[][] boardData)
	{
		// clear up the canvas
		for (int row = 0; row < rows; row++)
		{
			for (int col = 0; col < cols; col++)
			{
				boardData[row][col] = EMPTY;
			}
		}
		
		// no one make a move, right now
		prevMove = new TTTMove(0, 0, EMPTY);
		currMove = prevMove;
		
		// no one wins now
		winner = DRAW;
	}
	
	/**
	 * Clear the board in preparation for a new game.
	 */
	public void clearBoard()
	{
		// reinitialize board
		initBoard(boardData);

		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Return the player ID occupying the cell at the given row and
	 * column, or the empty ID if the cell is empty.
	 * 
	 * @param r the row of the cell.
	 * @param c the column of the cell.
	 * @return the player ID occupying the given cell.
	 */
	public int getBoardData(int r, int c)
	{
		return boardData[r][c];
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Apply the given move to the game board.
	 * 
	 * @param move the move to be applied to the board.
	 */
	public void applyMove(TTTMove move)
	{
		mark(move.getRow(),move.getCol(),move.getPlayer());
		
		// update the current Move
		prevMove = currMove;
		currMove = move;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Undo the given move from the game board.
	 * 
	 * @param move the move to be undone from the board.
	 */
	public void undoMove(TTTMove move)
	{	
		unmark(move.getRow(),move.getCol());
		// also need to reset the winner
		winner = DRAW;
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Mark the given cell with the player ID taking the cell.
	 * 
	 * @param r the row of the cell.
	 * @param c the column of the cell.
	 * @param player the player ID taking the cell.
	 */
	private void mark(int r, int c, int player)
	{
		boardData[r][c] = player;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Mark the given cell as empty.
	 * 
	 * @param r the row of the cell.
	 * @param c the column of the cell.
	 */
	private void unmark(int r, int c)
	{
		boardData[r][c] = EMPTY;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Return whether the given cell of the board is empty.
	 * 
	 * @param r the row of the cell.
	 * @param c the column of the cell.
	 * @return true if the given cell is empty, false otherwise.
	 */
	public boolean isEmpty(int r, int c)
	{
		if (boardData[r][c] == EMPTY)
		{
			return true;
		}
		else
		{
			return false;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Return whether the game board is completely full and no more moves
	 * may be made.
	 * 
	 * @return true if the game board is completely full, false otherwise.
	 */
	public boolean isFull()
	{
		for (int row = 0; row < rows; row++)
		{
			for (int col = 0; col < cols; col++)
			{
				if (boardData[row][col] == EMPTY){
					return false;
				}
			}
		}
		
		
		return true;
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Determine whether the player with the given ID has won the game.
	 * 
	 * @param player the player ID.
	 * @return true if the given player has won the game, false otherwise.
	 */
	public boolean isWin(int player)
	{	
		return winner == player;
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Determine whether the current game has ended.
	 * 
	 * @return true if the game is in an ending state, false otherwise.
	 */
	public boolean gameIsOver()
	{	
		
		
		/*			<1>               <2>                   <3>
		 *       (i-2,j-2)          (i-2,j)			    (i-2,j+2)
		 *                (i-1,j-1) (i-1,j)  (i-1,j+1)
		 *       (i,j-2)  (i,j-1)   (i,j)    (i,j+1)    (i,j+2)     <4>
		 *                (i+1,j-1) (i+1,j)  (i+1,j+1)
		 *       (i+2,j-2)         	(i+2,j)				(i+2,j+2) 
		 */
		
		// only to see whether the current move will cause a win
		if (currMove.getPlayer() != EMPTY){
				int r = currMove.getRow();
				int c = currMove.getCol();
				int player = currMove.getPlayer();
			
			// <1>
			if (findTTT(r-2,c-2,r-1,c-1,r+1,c+1,r+2,c+2,player)){
				winner = player;
				return true;
			}
			// <2>
			if (findTTT(r-2,c,r-1,c,r+1,c,r+2,c,player)){
				winner = player;
				return true;
			}
			// <3>
			if (findTTT(r-2,c+2,r-1,c+1,r+1,c-1,r+2,c-2,player)){
				winner = player;
				return true;
			}
			// <4>
			if (findTTT(r,c+2,r,c+1,r,c-1,r,c-2,player)){
				winner = player;
				return true;
			}
			
			
			
			// second let us see if the board is full
			if (isFull())
				return true;
			
			// all do not match, then no win
			return false;
				
		}
		
		// EMPTY means have not begin thus no wins
		return false;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean findTTT(int x1, int y1, int x2, int y2, int x3, int y3,
		int x4, int y4, int player){
		
		// first 3
		if (markEquals(x1,y1,player) == true && markEquals(x2,y2,player) == true)
			return true;
		
		// middle 3
		if (markEquals(x2,y2,player) == true && markEquals(x3,y3,player) == true)
			return true;
		// final 3
		if (markEquals(x3,y3,player) == true && markEquals(x4,y4,player) == true)
			return true;
			
		return false;
	}
	
	/**
	 * markEquals will judge whether the specific position ID retrieve by row, col on board,
	 * will match the given ID  
	 * @param row the row you want to check
	 * @param col the column you want to check
	 * @param player the ID you want to check
	 * @return whether the value match
	 */
	public boolean markEquals(int row, int col, int player)
	{
		// check whether the coords valid
		if (row < 0 || row >= this.rows)
			return false;
		if (col < 0 || col >= this.cols)
			return false;
		
		// check value
		if (boardData[row][col] == player)
			return true;
		else
			return false;
	}
	
	/**
	 * Return the player marking of the given cell of the board.
	 *  
	 * @param r the row of the cell.
	 * @param c the column of the cell.
	 * @return the player marking of the given cell of the board. 
	 */
	public char getBoardMark(int r, int c)
	{
		int value = boardData[r][c];
		
		if (value == PLAYER_1)
		{
			return PLAYER_1_MARK;
		}
		else if (value == PLAYER_2)
		{
			return PLAYER_2_MARK;
		}
		else
			return EMPTY_MARK;
			
		//throw new RuntimeException("You must implement this method!");
	}
	
	/*
	 * The following are a few basic functions that you may
	 * find useful. 
	 */ 
	
	/**
	 * Return the board marking corresponding to the given player ID.
	 * 
	 * @param player the player ID.
	 * @return the board marking of the given player.
	 */
	public char getPlayerMark(int player)
	{
		if (player == PLAYER_1)
			return PLAYER_1_MARK;
		else if (player == PLAYER_2)
			return PLAYER_2_MARK;
		return EMPTY_MARK;
	}
	
	/**
	 * Prints the current board state to standard-out.
	 */
	public void printBoard()
	{
		System.out.println(this);
	}
	
	/**
	 * Give a string representation of the current board state.
	 * 
	 * @return a visual represention of the current board state.
	 */
	public String toString()
	{
		String output = "";
		int r, c, i;
		for (r = 0; r < rows; r++)
		{
			for (c = 0; c < cols; c++)
			{
				output += "" + getBoardMark(r, c);
				if (c != cols - 1)
				{
					output += "|";
				}
			}
			output += "\r\n";
			if (r != rows - 1)
			{
				for (i = 0; i < cols-1; i++)
				{
					output += "-+";
				}
				output += "-\r\n";
			}
		}
		return output;
	}
	
}
